home *** CD-ROM | disk | FTP | other *** search
/ PC Media 2 / PC MEDIA CD02.iso / share / udos / fgrep103 / makeskip.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-29  |  1.7 KB  |  53 lines
  1. #include "bm.h"
  2. #include "proto.h" /* N2 04-05-91 */
  3. #include <alloc.h> /* N2 04-05-91 */
  4. #include <stdlib.h> // 11-28-91
  5.  
  6. /* extern char *calloc(); */
  7.  
  8. void MakeSkip(char Pattern[],int Skip1[],int Skip2[],int PatLen)
  9.      /* generate the skip tables for Boyer-Moore string search algorithm.
  10.      * Skip1 is the skip depending on the character which failed to match
  11.      * the pattern, and Skip2 is the skip depending on how far we got into
  12.      * the pattern. Pattern is the search pattern and PatLen is strlen(Pattern) */
  13.      {
  14.         int *BackTrack; /* backtracking table for t when building skip2 */
  15.         int c;          /* general purpose constant */
  16.         int j,k,t,tp;   /* indices into Skip's and BackTrack */
  17.  
  18.         BackTrack = (int *)calloc(PatLen,sizeof(int));
  19.         for (c=0; c<=MAXCHAR; ++c)
  20.          {
  21.           Skip1[c] = PatLen;
  22.          }
  23.         for (k=0;k<PatLen;k++)
  24.          {
  25.           Skip1[Pattern[k]] = PatLen-k-1;
  26.           Skip2[k] = 2 * PatLen-k-1;
  27.          } /* for */
  28.         for (j = PatLen-1,t = PatLen;j >= 0; --j,--t)
  29.          {
  30.           BackTrack[j] = t;
  31.           while (t<PatLen && Pattern[j] != Pattern[t])
  32.            {
  33.             Skip2[t] = min(Skip2[t], PatLen-j-1);
  34.             t = BackTrack[t];
  35.            } /* while */
  36.          } /* for */
  37.         for (k = 0;k <= t;++k)
  38.          {
  39.       Skip2[k] = (int)min(Skip2[k],PatLen+t-k);
  40.          }
  41.         tp=BackTrack[t];
  42.         while(tp<PatLen)
  43.          {
  44.           while(t<PatLen)
  45.            {
  46.             Skip2[t] = min(Skip2[t],tp-t+PatLen);
  47.             ++t;
  48.            } /* while */
  49.           tp = BackTrack[tp];
  50.          } /* while */
  51.         free(BackTrack);
  52.      } /* MakeSkip */
  53.